package chapter01;

public class FirstMissingPositive {
    /**
     * 在不使用额外数据结构并且时间复杂度为O(n)情况下，我们尽量使用原有的数组作为额外的空间进行变化
     *  原位偏移
     *      从头遍历数组 我们规定数字1存放在[1]位置 但下标从0开始 所以数字i存放在[i-1]位置上
     *      但所求是正整数 即[1->N] 在数组长度为length情况下  数组中存储的正整数范围为[1->length]
     *      因此在遍历数组的情况下 当[i]的值在[1->length]范围内 将[i]与[[i]-1]交换
     *      最后遍历数字 当[i]!=i+1 i+1即为所求  当遍历为都没找到时 length+1为所求
     *  细节
     *      在交换的时候可以发现，当[i]与[[i]-1]值相等时，会进入死循环，因此要添加一个条件，即[i]！=[[i]-1]
     */
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=1&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){
                int temp=nums[nums[i]-1];
                nums[nums[i]-1]=nums[i];
                nums[i]=temp;
                i--;
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }
}
